package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/*
https://leetcode.cn/problems/symmetric-tree/description/
https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
 */
class leetcode_101 {
    @Test
    fun test_1() {
        val root = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n2_v2 = TreeNode(2)
        val n3_v2 = TreeNode(3)
        val n4_v2 = TreeNode(4)
        root.left = n2
        n2.left = n3
        n2.right = n4
        root.right = n2_v2
        n2_v2.left = n4_v2
        n2_v2.right = n3_v2
        val actual = isSymmetric(root)
        val expect = true
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_2() {
        val root = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n2_v2 = TreeNode(2)
        val n3_v2 = TreeNode(3)
        root.left = n2
        n2.right = n3
        root.right = n2_v2
        n2_v2.right = n3_v2
        val actual = isSymmetric(root)
        val expect = false
        Assert.assertEquals(expect, actual)
    }

    private fun isSymmetric(root: TreeNode?): Boolean {
        // return isSymmetric1(root)
        return isSymmetric2(root)
    }

    private fun isSymmetric1(root: TreeNode?): Boolean {
        // 层级遍历
        // T - N
        // S - N
        if (root == null) {
            return true
        }
        val queue: LinkedList<TreeNode?> = LinkedList<TreeNode?>()
        queue.offer(root.left)
        queue.offer(root.right)

        while (!queue.isEmpty()) {
            val left: TreeNode? = queue.poll()
            val right: TreeNode? = queue.poll()

            // 终止条件
            if (left == null && right === null) {
                continue
            }

            if (left == null && right != null) {
                return false
            }

            if (left != null && right == null) {
                return false
            }

            if (left != null && right != null) {
                if (left.`val` != right.`val`) {
                    return false
                } else {
                    queue.offer(left.left)
                    queue.offer(right.right)
                    queue.offer(left.right)
                    queue.offer(right.left)
                }
            }
        }
        return true
    }

    private fun isSymmetric2(root: TreeNode?): Boolean {
        if (root == null) {
            return true
        }
        return isSymmetric(root.left, root.right)
    }

    private fun isSymmetric1(left: TreeNode?, right: TreeNode?): Boolean {
        // 深度遍历：后序遍历 左右中，右左中 - 递归
        // T - N
        // S - N
        // 终止条件
        if (left == null && right == null) return true
        if (left != null && right == null) return false
        if (left == null && right != null) return false
        if (left != null && right != null) {
            if (left.`val` != right.`val`) return false
        }

        // 左孩子：左右中，右孩子：右左中
        // 左孩子 - 左 ｜ 右孩子 - 右
        val isMatched1: Boolean = isSymmetric1(left?.left, right?.right)
        // 左孩子 - 右 ｜ 右孩子 - 左
        val isMatched2: Boolean = isSymmetric1(left?.right, right?.left)
        // 左孩子 - 中 ｜ 右孩子 - 中
        val isMatched = isMatched1 == true && isMatched2 == true
        return isMatched
    }

    fun isSymmetric(left: TreeNode?, right: TreeNode?): Boolean {
        /*
         * 深度遍历 - 前序遍历
         *
         * 思路：
         * 当左空、右空时，则对称
         * 当左非空、右空时，则不对称
         * 当左空、非右空时，则不对称
         * 当非左空、非右空时，则继续判断：
         *      当节点值不同，则不对称
         *      当节点值同，则继续判断：
         *          左孩子对称 && 右孩子对称，则对称
         */
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (null == left && null == right) {
            return true
        }

        if (null == left && null != right) {
            return false
        }

        if (null != left && null == right) {
            return false
        }
        // 3 确定单次递归的处理逻辑：前序遍历
        // 中
        if (null != left && null != right) {
            if (left.`val` != right.`val`) {
                return false
            }
            // 左
            val isLeft = isSymmetric(left.left, right.right)
            if (!isLeft) {
                return false
            }

            // 右
            val isRight = isSymmetric(left.right, right.left)
            if (!isRight) {
                return false
            }
            return true
        }
        return false
    }
}